package Solutions

import "fmt"

func checkIfPrerequisite(numCourses int, prerequisites [][]int, queries [][]int) []bool {
	var parent = make([][]int, numCourses)
	for i := 0; i < numCourses; i++ {
		parent[i] = make([]int, 0, 3)
	}
	for _, pre := range prerequisites {
		parent[pre[1]] = append(parent[pre[1]], pre[0])
	}
	var ans = make([]bool, len(queries))
	cache := make([]map[int]struct{}, numCourses)
	// for i := 0; i < numCourses; i++ {
	// 	cache[i] = nil
	// }
	var dfs func(i int) map[int]struct{}
	dfs = func(i int) map[int]struct{} {
		if cache[i] != nil {
			return cache[i]
		}

		var mps = make([]map[int]struct{}, len(parent[i]))
		for ind, v := range parent[i] {
			mps[ind] = dfs(v)
		}
		sum := 0
		for ind := 0; ind < len(mps); ind++ {
			sum += len(mps[ind])
		}
		var mp = make(map[int]struct{}, sum+len(parent[i]))
		for _, v := range parent[i] {
			mp[v] = struct{}{}
		}
		for ind := 0; ind < len(mps); ind++ {
			for k := range mps[ind] {
				mp[k] = struct{}{}
			}
		}
		cache[i] = mp
		return mp
	}
	for ind, query := range queries {
		mp := dfs(query[1])
		if _, ok := mp[query[0]]; ok {
			ans[ind] = true
		}

	}
	fmt.Println(cache)
	return ans
}
